The problem can be found at the following link: Question Link
This is a greedy problem, to solve this problem:
- Firstly I creating a structure
meet
to represent meeting details, including start time, end time, and index. - Then, I sort the meetings based on their finish times using a comparison function
comp
. - After sorting, I iterate through the sorted list of meetings, selecting each meeting only if its start time is strictly greater than the finish time of the previous meeting which I stored in
last
variable. This ensures that the selected meetings do not overlap, allowing us to manage as many meetings as possible while maximizing the non-overlapping intervals. - The final step involves returning the indices of the selected meetings.
- Time Complexity:
O(N log N)
for sorting, where N is the number of meetings. - Auxiliary Space Complexity:
O(N)
for thev
vector.
class Solution {
public:
struct meet {
int start, end, index;
};
static bool comp(struct meet& a, struct meet& b) {
if (a.end == b.end)
return a.start < b.start;
return a.end < b.end;
}
vector<int> maxMeetings(int N, vector<int>& S, vector<int>& F) {
vector<meet> v;
vector<int> out;
for (int i = 0; i < N; ++i)
v.push_back({S[i], F[i], i + 1});
sort(v.begin(), v.end(), comp);
int last = 0;
for (auto i : v)
if (last < i.start) {
last = i.end;
out.push_back(i.index);
}
sort(out.begin(), out.end());
return out;
}
};
For discussions, questions, or doubts related to this solution, please visit our discussion section. We welcome your input and aim to foster a collaborative learning environment.
If you find this solution helpful, consider supporting us by giving a ⭐ star
to the getlost01/gfg-potd repository.